package 单周赛.history;

import util.ListNode;

/**
 *
 */
public class 第281场单周赛 {

    public static void main(String[] args) {

        String str = "cczazcc";
        System.out.println(new 第281场单周赛().repeatLimitedString(str, 3));

    }

    /**
     * 6012. 统计各位数字之和为偶数的整数个数 显示英文描述
     * 题目难度Easy
     * 给你一个正整数 num ，请你统计并返回 小于或等于 num 且各位数字之和为 偶数 的正整数的数目。
     * 正整数的 各位数字之和 是其所有位上的对应数字相加的结果。
     * <p>
     * 模拟
     * 通过对10取模获取个位数
     * 让后/10去除各个位数
     *
     * @param num
     * @return
     */
    public int countEven(int num) {
        int ans = 0;
        for (int i = 1; i <= num; i++) {
            if (isOu(i)) {
                ans++;
            }
        }
        return ans;
    }

    public boolean isOu(int num) {
        int total = 0;
        while (num > 0) {
            total += num % 10;
            num /= 10;
        }
        return total % 2 == 0;
    }

    /**
     * 6013. 合并零之间的节点 显示英文描述
     * 题目难度Medium
     * 给你一个链表的头节点 head ，该链表包含由 0 分隔开的一连串整数。链表的 开端 和 末尾 的节点都满足 Node.val == 0 。
     * 对于每两个相邻的 0 ，请你将它们之间的所有节点合并成一个节点，其值是所有已合并节点的值之和。然后将所有 0 移除，修改后的链表不应该含有任何 0 。
     * 返回修改后链表的头节点 head 。
     *
     * @param head
     * @return
     */
    public ListNode mergeNodes(ListNode head) {
        ListNode curNode = head;
        while (curNode.next != null) {
            if (curNode.next.val != 0) {  //如果下个节点值不为0，下个节点值累计到当前节点，并删除下个节点
                curNode.val += curNode.next.val;
                curNode.next = curNode.next.next;
            } else {  //如果下个节点为0，则移动节点
                curNode = curNode.next;
            }
            if (curNode.next.next == null) {  //去除最后一个0节点
                curNode.next = null;
            }
        }
        return head;
    }

    /**
     * 6014. 构造限制重复的字符串 显示英文描述
     * 题目难度Medium
     * 给你一个字符串 s 和一个整数 repeatLimit ，用 s 中的字符构造一个新字符串 repeatLimitedString ，
     * 使任何字母 连续 出现的次数都不超过 repeatLimit 次。你不必使用 s 中的全部字符。
     * 返回 字典序最大的 repeatLimitedString 。
     * <p>
     * 如果在字符串 a 和 b 不同的第一个位置，字符串 a 中的字母在字母表中出现时间比字符串 b 对应的字母晚，
     * 则认为字符串 a 比字符串 b 字典序更大 。如果字符串中前 min(a.length, b.length) 个字符都相同，那
     * 么较长的字符串字典序更大。
     *
     * @param s
     * @param repeatLimit
     * @return
     */
    public String repeatLimitedString(String s, int repeatLimit) {
        StringBuilder stringBuilder = new StringBuilder();
        int[] total = new int[26];
        for (int i = 0; i < s.length(); i++) {
            total[s.charAt(i) - 'a']++;
        }
        while (true) {
            for (int i = 25; i >= 0; i--) {
                if (i == 0 && total[0] == 0) {
                    return stringBuilder.toString();
                }
                if (total[i] == 0) continue;
                if (total[i] <= repeatLimit) {
                    for (int j = 0; j < total[i]; j++) {
                        if (isLimit(stringBuilder, (char) (i + 'a'), repeatLimit)) {
                            for (int pre = 0; pre < i; pre++) {
                                if (total[pre] > 0) {
                                    stringBuilder.append((char) (pre + 'a'));
                                    total[pre]--;
                                    break;
                                }
                                if (pre == 0) return stringBuilder.toString();  //没有找到小一些的字母
                            }
                        }
                        stringBuilder.append((char) (i + 'a'));
                    }
                    total[i] = 0;
                    i = 25;
                } else {
                    for (int j = 0; j < repeatLimit; j++) {
                        if (isLimit(stringBuilder, (char) (i + 'a'), repeatLimit)) {
                            for (int pre = 0; pre < i; pre++) {
                                if (total[pre] > 0) {
                                    stringBuilder.append((char) (pre + 'a'));
                                    total[pre]--;
                                    break;
                                }
                                if (pre == 0) return stringBuilder.toString();  //没有找到小一些的字母
                            }
                        }
                        stringBuilder.append((char) (i + 'a'));
                    }
                    total[i] -= repeatLimit;
                    i = 25;
                }
                if (i == 0 && total[0] == 0) {
                    return stringBuilder.toString();
                }
            }
        }
    }

    public boolean isLimit(StringBuilder builder, char ch, int limit) {
        if (builder.length() >= limit) {
            for (int i = builder.length() - 1; i >= 0 && limit > 0; i--) {
                limit--;
                if (builder.charAt(i) != ch) {
                    return false;
                }
            }
        } else {
            return false;
        }
        return true;
    }

}
